package org.laizili.solution.leetcode;

import org.laizili.structure.tree.bitree.TreeNode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * <a href="https://leetcode.cn/problems/all-elements-in-two-binary-search-trees/">1305. 两棵二叉搜索树中的所有元素</a>
 * <p>
 * tags: 二叉搜索树(BST)中序遍历;
 */
public class Problem1305 {

    private static class Solution {
        public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
            List<Integer> res = new ArrayList<>();
            Deque<TreeNode> stack1 = new ArrayDeque<>();
            Deque<TreeNode> stack2 = new ArrayDeque<>();
            // 栈记录遍历路径
            addToStack(root1, stack1);
            addToStack(root2, stack2);
            TreeNode cur1;
            TreeNode cur2;
            while (!stack1.isEmpty() && !stack2.isEmpty()) {
                cur1 = stack1.peek();
                cur2 = stack2.peek();
                if (cur1.val < cur2.val) {
                    res.add(cur1.val);
                    stack1.pop();
                    if (cur1.right != null) {
                        addToStack(cur1.right, stack1);
                    }
                } else {
                    res.add(cur2.val);
                    stack2.pop();
                    if (cur2.right != null) {
                        addToStack(cur2.right, stack2);
                    }
                }
            }
            while (!stack1.isEmpty()) {
                cur1 = stack1.pop();
                res.add(cur1.val);
                if (cur1.right != null) {
                    addToStack(cur1.right, stack1);
                }
            }
            while (!stack2.isEmpty()) {
                cur2 = stack2.pop();
                res.add(cur2.val);
                if (cur2.right != null) {
                    addToStack(cur2.right, stack2);
                }
            }
            return res;
        }

        private void addToStack(TreeNode root, Deque<TreeNode> stack) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
        }
    }
}
